# -*- coding: utf-8 -*-

"""偶图的最大匹配问题，匈牙利算法。其实这个算法在RL很有用，许多业务用大最大匹配。"""

class Hungarian():
    def __init__(self) -> None:
        pass

    def max_match(self, bipartGraph: list):
        """用下标来代表顶点，
        bipartGraph:= 
        [
            {1,2,5},     # 0 号顶点邻接的顶点
            {3,6},       # 1 号顶点邻接的顶点
            {7,12,9},    # 2 号顶点邻接的顶点
            ...
            {i,j,k}      # n 号顶点邻接的顶点
        ]"""
        visited = set()    # 已经预定配对的顶点
        determined = [None for _ in range(len(bipartGraph))]    # 各号顶点预定配对的顶点
        oll = set(range(len(bipartGraph)))    # 所有的顶点

        def letmatch(u, v0):
            """为 u 找配对，但不与 v0 匹配, 让掉 v0"""
            for v in bipartGraph[u]:
                if v == v0:
                    continue

                bingo = False
                if v not in visited:
                    bingo = True
                elif letmatch(determined[v], v):    # 先看看别人能不能让出来
                    bingo = True

                # 只有别人也让得出来自己才能更新匹配情况
                if bingo:
                    visited.update({u, v})
                    determined[u], determined[v] = v, u
                    return True

            return False

        for u in oll:
            if u in visited:
                continue

            for v in bipartGraph[u]:
                bingo = False
                if v not in visited:
                    bingo = True
                elif letmatch(determined[v], v):
                    bingo = True

                if bingo:
                    visited.update({u, v})
                    determined[u], determined[v] = v, u
                    break

        return determined


if __name__ == '__main__':
    hungarian = Hungarian()
    bipartGraph = [
        {5,7}
       ,{5}
       ,{4,6}
       ,{7}
       ,{2}
       ,{0,3}
       ,{2}
       ,{0,3}
    ]

    determined = hungarian.max_match(bipartGraph)

    print(determined)
